import java.util.Arrays;

public class CoinChange {
    public int coinChange4(int[] coins, int amount) {
        return process1(coins, amount, 0);
    }

    public int process(int[] coin, int amount, int i, int[][] dp) {
        if (amount < 0) return -1;
        if (dp[amount][i] != -2) {
            return dp[amount][i];
        } else if (amount == 0) {
            dp[amount][i] = 0;
        } else if (i == coin.length) {
            dp[amount][i] = -1;
        } else {
            int no;
            int yes;
            int min = Integer.MAX_VALUE;
            for (int j = i; j < coin.length; j++) {
                no = process(coin, amount, j + 1, dp);
                yes = process(coin, amount - coin[j], j, dp);
                if (no == -1 && yes == -1) continue;
                if (no == -1) {
                    min = Math.min(yes + 1, min);
                } else if (yes == -1) {
                    min = Math.min(min, no);
                } else {
                    min = Math.min(Math.min(min, no), yes + 1);
                }
            }
            dp[amount][i] = min == Integer.MAX_VALUE ? -1 : min;
        }
        return dp[amount][i];
    }


    public int coinChange1(int[] coins, int amount) {
        int[][] dp = new int[amount + 1][coins.length + 1];
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = 0;
        }
        for (int i = 0; i < dp.length; i++) {
            dp[i][coins.length] = -1;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = coins.length - 1; j >= 0; j--) {
                int no;
                int yes;
                int min = Integer.MAX_VALUE;
                for (int k = j; k < coins.length; k++) {
                    no = dp[i][k + 1];
                    yes = -1;
                    if (i - coins[k] >= 0) {
                        yes = dp[i - coins[k]][k];
                    }
                    if (no == -1 && yes == -1) continue;
                    if (no == -1) {
                        min = Math.min(yes + 1, min);
                    } else if (yes == -1) {
                        min = Math.min(min, no);
                    } else {
                        min = Math.min(Math.min(min, no), yes + 1);
                    }
                }
                dp[i][j] = min == Integer.MAX_VALUE ? -1 : min;
            }
        }
        return dp[amount][0];
    }

    public int process1(int[] coins, int i, int amount) {
        if (i == coins.length) {
            return amount == 0 ? 0 : -1;
        }
        int min = Integer.MAX_VALUE;
        for (int j = 0; amount - coins[i] * j >= 0; j++) {
            int k = process1(coins, i + 1, amount - coins[i] * j);
            if (k != -1) {
                min = Math.min(min, k + j);
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }

    public int coinChange2(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        for (int i = 1; i <= amount; i++) {
            dp[n][i] = -1;
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 1; j < amount + 1; j++) {
                if (j - coins[i] >= 0) {
                    if (dp[i][j - coins[i]] != -1 && dp[i + 1][j] != -1) {
                        dp[i][j] = Math.min(dp[i][j - coins[i]] + 1, dp[i + 1][j]);
                    } else if (dp[i][j - coins[i]] != -1 || dp[i + 1][j] != -1) {
                        dp[i][j] = dp[i + 1][j] == -1 ? dp[i][j - coins[i]] + 1 : dp[i + 1][j];
                    } else {
                        dp[i][j] = -1;
                    }
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        return dp[0][amount];
    }

    public int coinChange3(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n][amount + 1];
        Arrays.fill(dp[0], Integer.MAX_VALUE);
        for (int i = 0; i * coins[0] <= amount; i++) {
            dp[0][i * coins[0]] = i;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < amount + 1; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - coins[i] >= 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i]] == Integer.MAX_VALUE ? dp[i][j - coins[i]] : dp[i][j - coins[i]] + 1);
                }
            }
        }
        return dp[n - 1][amount] == Integer.MAX_VALUE ? -1 : dp[n - 1][amount];
    }

    public int coinChange5(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        for (int i = 0; i < n + 1; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < amount + 1; j++) {
                for (int k = 0; j - k * coins[i] >= 0; k++) {
                    if (dp[i][j - k * coins[i]] != Integer.MAX_VALUE)
                        dp[i + 1][j] = Math.min(dp[i][j - k * coins[i]] + k, dp[i + 1][j]);
                }
            }
        }
        return dp[n][amount] == Integer.MAX_VALUE ? -1 : dp[n][amount];
    }

    public static void main(String[] args) {
        int[] nums = {1,2,5};
        System.out.println(new CoinChange().coinChange(nums, 11));
    }

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int coin : coins) {
            for (int i = coin; i < amount + 1; i++) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}